// 递归
// 本质是：解决主问题时，发现相同子问题，解决主问题和子问题的方法相同 (主问题有可能就是子问题)
// 心理暗示：宏观看待递归问题，把递归函数当成黑盒，相信这个黑盒一定能完成任务
// 技巧：
//      找到重复子问题 -> 设计函数头
//      子问题是如何解决的 -> 函数体的书写
//      注意递归函数的出口 -> 关注问题不能分割的情况
// 拓展：如果一个题目可以用决策树画出来，那么也可以通过递归解决

// 例题 3：
// 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//
//
//        示例 1：
//
//
//        输入：head = [1,2,3,4,5]
//        输出：[5,4,3,2,1]
//        示例 2：
//
//
//        输入：head = [1,2]
//        输出：[2,1]
//        示例 3：
//
//        输入：head = []
//        输出：[]
//
//
//        提示：
//
//        链表中节点的数目范围是 [0, 5000]
//        -5000 <= Node.val <= 5000
//
//
//        进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

// 解题思路：
// 逆置链表，可以拿出一个节点，将后面的节点逆置
// 再把这个节点接在逆置链表的后面

public class ReverseList {
    public ListNode reverseList(ListNode head) {
        if(head ==  null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        ListNode next = head.next;
        next.next = head;
        head.next = null;
        return newHead;
    }
}
